package 链表题.反转单向链表;

import 链表题.ListNode;

public class Test2 {
    /**
     * 方法二: 与方法一类似, 构造一个新链表, 从旧链表的头部移除节点,
     * 添加到新链表头部, 完成后新链表就是倒序的, 区别在于原题目未提
     * 供节点外层的容器类, 这里提供一个, 另一个区别是并不去构造新节点
     */


    public class List {
        ListNode head;

        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (first == null) {
                return null;
            }
            head = head.next;
            return first;
        }
    }

    public ListNode reverseList(ListNode head) {
        List list1 = new List(head);
        List list2 = new List(null);
        while (true) {
            ListNode remove = list1.removeFirst();
            if (remove == null) {
                break;
            }
            list2.addFirst(remove);
        }
        return list2.head;
    }

    public static void main(String[] args) {
        ListNode o5 = new ListNode(5,null);
        ListNode o4 = new ListNode(4,o5);
        ListNode o3 = new ListNode(3,o4);
        ListNode o2 = new ListNode(2,o3);
        ListNode o1 = new ListNode(1,o2);
        System.out.println(o1);
        ListNode n1 = new Test2().reverseList(o1);
        System.out.println(n1);
    }
}
